\section{Concluding remarks and open questions}
We studied the fundamental $k$-gossip problem in dynamic networks and
showed a lower bound of $\Omega(n + nk/\log n)$ rounds for any token
forwarding algorithm against a strongly adaptive adversary,
significantly improving over the previous best bound of $\Omega(n\log
k)$~\cite{kuhn+lo:dynamic} for sufficiently large $k$.  Our lower
bound matches the known upper bound of $O(nk)$ up to a logarithmic
factor, and establishes a near-linear factor separation between
token-forwarding and network-coding based algorithms.  While our bound
rules out significantly faster algorithms in the strongly adaptive
adversary model, we complement our lower bound by presenting the
\symdiff\ protocol for a weakly adaptive adversary.  We show that
\symdiff\ is near-optimal when the starting distribution is
well-mixed.  Intuitively, a well-mixed distribution captures the
``hard" regime for information spreading in the adversarial setting,
when most nodes have most of the tokens.  Perhaps, the most
interesting problem left open by our work is the analysis of
\symdiff\ in the weakly adaptive adversary model for an {\em
  arbitrary}\/ starting distribution. \junk{ A main conjecture of our
  paper is that the \symdiff protocol gives near-linear time for {\em
    any} starting distribution.}  \junk{An interesting feature of
  \symdiff protocol is that it needs techniques from communication
  complexity for efficient implementation.}

\junk{
Our almost-tight lower bound of $\Omega(n + nk/\log n)$ rounds extends
to randomized algorithms with an adaptive adversary that makes its
decision in each round with knowledge of the randomness of the
algorithm in that round (but without knowledge of future randomness).
}

We also presented offline algorithms for $k$-gossip.  An important
intermediate model between the offline setting and the adaptive
adversary models is the oblivious adversary model in which the
adversary lays the dynamic network in advance (as in the offline
setting), but the changing topology is revealed to the algorithm one
round at a time.  Finally, this paper has focused on models in which
at most one token is sent per edge per round and the network can
change every round.  Subsequent to the announcement of our lower
bound~\cite{arxiv}, the argument has been extended to the model where
multiple tokens can be broadcast and the dynamic network is required
to contain a stable subgraph for multiple rounds~\cite{personal}.

\junk{For the important practical case of small token sizes (e.g., $O(\log
n)$ bits) even the best online gossip algorithm we know based on
network coding takes $O(n^2/\log n)$ rounds~\cite{haeupler+k:dynamic}.
In contrast, we show that in the offline setting there exist
 token-forwarding algorithms that run in
$O(n^{1.5}\sqrt{\log n})$ time.  What is the best possible time
achievable for gossip with small token sizes?}

\junk{
Finally, a major question is whether we can design fully distributed
fast (e.g., $O(\min\{n\sqrt{\log k}, nk\})$ time) token-forwarding
algorithms for general dynamic networks under an offline adversary or,
even better, an oblivious adversary.  We believe that our first
centralized algorithm can be made distributed and will be useful in
resolving this question.}

\junk{Finally, in a recent work \cite{rw-podc}, our Algorithm 1 has been
directly adapted to yield a distributed token forwarding algorithm for
information spreading, albeit in a {\em restricted} model of dynamic
networks where it is assumed that the spectral properties of the
networks don't change.  This distributed algorithm has subquadratic
running time only under certain conditions (e.g., the network should
have small dynamic diameter) and is slower in general than the
$O(\min\{n\sqrt{\log k}, nk\})$ round algorithm of this paper.  A
major question is whether we can design fully distributed fast (e.g.,
$O(\min\{n\sqrt{\log k}, nk\})$ time) token-forwarding algorithms for
general dynamic networks under an offline adversary or, even better,
an oblivious adversary.  We believe that the techniques introduced in
this paper will be useful in tackling this question.
}
